//实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。 
//
// 
//
// 示例 1： 
//
// 
//输入：x = 2.00000, n = 10
//输出：1024.00000
// 
//
// 示例 2： 
//
// 
//输入：x = 2.10000, n = 3
//输出：9.26100 
//
// 示例 3： 
//
// 
//输入：x = 2.00000, n = -2
//输出：0.25000
//解释：2⁻² = 1/2² = 1/4 = 0.25 
//
// 
//
// 提示： 
//
// 
// -100.0 < x < 100.0 
// -2³¹ <= n <= 2³¹-1 
// -10⁴ <= xⁿ <= 10⁴ 
// 
//
// 
//
// 注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/ 
// Related Topics 递归 数学 👍 302 👎 0


package leetcode.editor.cn;

//Java：数值的整数次方
public class ShuZhiDeZhengShuCiFangLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZhiDeZhengShuCiFangLcof().new Solution();
        // TO TEST
//        System.out.println(solution.myPow(0, -1));
        System.out.println(solution.myPow(2, 1 << 31));
//        System.out.println(solution.myPow(2, 2<<30));
        // n == 1
        System.out.println(1 << 31 == -1 << 31);
        System.out.println((1 << 30) * 2 == 1 << 31);

        System.out.println((-1 << 30) + "  " + (1 << 30));
        System.out.println((1 << 31) < -(1 << 30));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * @param x
         * @param n -2^31 <= n <= 2^31-1
         * @return
         */
        public double myPow(double x, int n) {
            if (n == 0 || x == 1)
                return 1;
            if (x == 0)
                return 0;
            double result = 1, t = x;
            // 1 << 31 int取不下，long可以取下啊
            long b = n;
            if (b < 0)
                b = -b;
            // n数值太大，会导致栈溢出
            // 分治思想
            while (b > 0) {
                // 每次把多出来的一项存入result
                if (b % 2 == 1) result = result * t;
                t = t * t;
                b = b >> 1;
            }
            if (n < 0) {
                result = 1 / result;
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
